package com.leetcode.二叉树.广度优先;

import java.util.LinkedList;
import java.util.Queue;

import com.leetcode.二叉树.广度优先.L116填充每个节点的下一个右侧节点指针.Node;

/**
 * 给定一个二叉树

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。
 * @author LZF
 *
 */
public class L117填充每个节点的下一个右侧节点指针II {
	/**
	 * 该题目跟L116的区别就是，这个题目给的是一个普通的二叉树，L116给的是一个完全二叉树
	 * 思路跟代码是一摸一样的，因为不管是普通的迭代还是优化后的迭代，在迭代孩子的时候，我们都有进行判断是否为空。
	 * 
	 * 以下代码跟思路解析跟L116一摸一样。
	 */
	
	/**
	 * 方法二：不用队列，效率更好。方法一的效率是比较低的，因为所有的节点都经过入队和出队，使得速度比较慢。
	 * 我们可以利用这道题的特性，优化一下：
	 * 1、对于每一层，都可以看成是一个(单)链表
	 * 2、我们的步骤是一层一层将链表链接起来，因此，当要链接这一层时，我们可以利用上一层链接好的链表，
	 * 	来指定这一层我们需要链接的是哪些节点，这些节点就是上一层链表的所有节点的左右孩子。
	 * 	遍历上一层的链表，就相当于遍历这一层的所有孩子
	 * 3、所以我们需要一些变量：①：pre:用于指向上一层链表的头	②：cur用来指向这一层的当前节点
	 * 	③：我们需要一个变量dummy(空包弹)，它是我们声明的一个节点，它的作用是用来指向这一层链表的头，方便传给下一层。
	 * 
	 * 题解可能比较难理解，如果画出来模拟一下就清晰多了。
	 */
	public Node connect2(Node root) {
		if(root == null) return root;
		//首先，第一层也就是root，只有一个节点，它的next肯定是null，所以第一层略过
		
		Node pre = root;//我们从第二层开始，所以pre初始化为第一层链表的头，也就是root
		//每一遍while循环就是一层
		while(pre != null) {
			Node dummy = new Node();//声明一个空包弹
			Node cur = dummy;//cur用来迭代
			while(pre != null) {
				//如果上一层节点的左孩子不为空，那么cur就往下迭代
				if(pre.left != null) {
					cur.next = pre.left;
					cur = cur.next;
				}
				//右孩子也是同理
				if(pre.right != null) {
					cur.next = pre.right;
					cur = cur.next;
				}
				pre = pre.next;//上一层的一个节点遍历完，指向下一个节点
			}
			//到这里pre为null，说明上一层的所有节点走完了，这一层的节点是上一层的孩子们也走完了，接下来走下一层
			pre = dummy.next;//这一层链表的头，传递给下一层
		}
		return root;
	}
	
	/**
	 * 方法一：用普通的迭代方法，利用队列，把每一层的节点的next都指向下一个节点
	 */
	public Node connect(Node root) {
		Queue<Node> que = new LinkedList<>();
		if(root != null) que.offer(root);
		while(!que.isEmpty()) {
			int len = que.size();//获取这一层的节点数
			//遍历到倒数第二个，当前节点的next指向下一个节点
			while(len > 1) {
				Node node = que.poll();//当前节点
				node.next = que.peek();//当前节点出队了，因此peek就是下一个节点
				//孩子入队
				if(node.left != null) que.offer(node.left);
				if(node.right != null) que.offer(node.right);
				len--;
			}
			//最后一个节点出队，它的next为null，默认也为null，因此不做事情，但是孩子需要入队
			Node node = que.poll();//当前节点
			//孩子入队
			if(node.left != null) que.offer(node.left);
			if(node.right != null) que.offer(node.right);
		}
		return root;
    }
	
	//树的定义
		class Node {
			public int val;
			public Node left;
			public Node right;
			public Node next;

			public Node() {
			}

			public Node(int _val) {
				val = _val;
			}

			public Node(int _val, Node _left, Node _right, Node _next) {
				val = _val;
				left = _left;
				right = _right;
				next = _next;
			}
		}
}
